package 中等.树;

import java.util.TreeMap;

/**
 * 给你一个下标从 0 开始的整数数组 nums 。
 * 如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：
 * i < j < k
 * nums[i] < nums[j] 且 nums[k] < nums[j]
 * 请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满
 * 足条件的三元组，返回 -1 。
 *
 * @ https://leetcode.cn/problems/minimum-sum-of-mountain-triplets-ii/description/
 * @date 2024/07/11
 */
public class 元素和最小的山形三元组II_2909 {

    public static void main(String[] args) {

        System.out.println(minimumSum(new int[]{8, 6, 1, 5, 3}));

    }

    /**
     * 左边用一个变量维护最小值，右边用平衡树维护最小值
     */
    public static int minimumSum(int[] nums) {
        int ans = Integer.MAX_VALUE;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>((a, b) -> a - b);

        for (int i = 2; i < nums.length; i++) {
            int num = nums[i];
            treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
        }
        int leftMin = nums[0];
        for (int i = 1; i < nums.length - 1; i++) {
            Integer rightMin = treeMap.firstEntry().getKey();

            if (nums[i] > leftMin && nums[i] > rightMin) {
                ans = Math.min(ans, nums[i] + leftMin + rightMin);
            }

            leftMin = Math.min(leftMin, nums[i]);

            int next = nums[i + 1];
            Integer cnt = treeMap.get(next);
            if (cnt == 1) {
                treeMap.remove(next);
            } else {
                treeMap.put(next, cnt - 1);
            }
        }

        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

}
